package 中等.贪心思想;

import java.util.Arrays;

/**
 * 给你一个下标从 0 开始的整数数组 nums 。你可以将 nums 中的元素按 任意顺序 重排（包括给定顺序）。
 * 令 prefix 为一个数组，它包含了 nums 重新排列后的前缀和。换句话说，prefix[i] 是 nums 重新排
 * 列后下标从 0 到 i 的元素之和。nums 的 分数 是 prefix 数组中正整数的个数。
 * 返回可以得到的最大分数。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/rearrange-array-to-maximize-prefix-score
 */
public class 重排数组以得到最大前缀分数_6316 {

    public static void main(String[] args) {

    }

    /**
     * 排序+贪心思想
     * 降序排序，使得前缀和尽可能大
     */
    public int maxScore(int[] nums) {
        // 注意数字溢出
        long sum = 0;

        Arrays.sort(nums);
        for (int i = nums.length - 1; i >= 0; i--) {
            sum += nums[i];
            if (sum <= 0) {
                return nums.length - 1 - i;
            }
        }

        return nums.length;
    }

}
